1. Field of the Invention
The invention relates to arbitration in a digital system and, in particular, to control of access to a bus by a plurality of requesting agents.
2. Description of Related Art
Arbitration schemes for controlling fair access of a plurality of agents to a bus are known. For example, U.S. Pat. No. 5,485,586 proposes queuing requests for access to a bus and then granting access in the order dictated by the queued requests.
While maintaining fairness is an important function of arbitration, it is also desirable that arbitration be done as simply and expeditiously as is practical. It is also advantageous if the arbitration scheme employed is capable of ensuring that access be granted within minimum time periods, e.g. fairness intervals, that may be specified for certain high-speed applications. As used herein, a xe2x80x9cfairness intervalxe2x80x9d is the time needed for all agents which are actually requesting access to the bus to be granted such access. For example, the IEEE 1394 High Performance Serial Bus Standard requires that, after receipt of a packet of information, if there is a need to retransmit the packet this must be done within four fairness intervals. In systems where access is granted in the order of queued requests, this requirement will not necessarily be met, but will depend on the order in which the requests are queued. In other words, the meeting of minimum-time-period requirements for access may be unpredictable. The IEEE 1394 Standard is particularly useful for high performance bus interconnection of computer peripherals and consumer electronics, and especially for the transmission of high-speed digital audio and video data over a bus.
It is an object of the invention to effect arbitration in a predictable and expeditious manner.
It is another object of the invention to provide the capability of ensuring bus access to each of a plurality of requesting agents within a specified minimum time period.
In accordance with the invention, a plurality of agents requesting access to a bus are serviced by:
providing a communication path for accepting requests from first and second pairs of requesting agents;
providing an indication of which of the requesting agents in the first pair was last considered for access to the bus;
providing an indication of which of the requesting agents in the second pair was last considered for access to the bus;
providing an indication of which of the pairs of requesting agents was last considered for access to the bus;
granting access to the requesting agents currently requesting access in accordance with the priority:
in the pair not last considered for access, the requesting agent not last considered for access;
in the pair not last considered for access, the requesting agent last considered for access;
in the pair last considered for access, the requesting agent not last considered for access;
in the pair last considered for access, the requesting agent last considered for access.
This approach of granting access automatically adapts to the number of agents that are actually making requests. As will be explained in detail, it also provides the capability of expanding arbitration to any number of requesting agents.